#include <list>
#include <stack>

using namespace std;

class Queue1
{
private:
    // C++ 中的双向链表 list
    // 单向链表就足够了
    list<int> l;

public:
    // 调用任何方法之前，先调用这个方法来判断队列内是否有东西
    bool empty()
    {
        return l.empty();
    }

    // 向队列中加入 x，加到尾巴
    // push 对应着 Java 队列中的 offer
    void push(int x)
    {
        l.push_back(x);
    }

    // 从队列拿，从头拿
    // 注：C++ 中的队列没有这个方法，与其对应的接口是 pop
    // 但是 pop 是不会返回数据的，直接 pop_front 即可
    int poll()
    {
        int ans = l.front();
        l.pop_front();
        return ans;
    }

    // 返回队列头的元素但是不弹出
    // front 对应着 Java 队列中的 peek
    int front()
    {
        return l.front();
    }

    // 返回目前队列里有几个数
    int size() 
    {
        return l.size();
    }

    // C++ 中的队列还会提供 back 接口，返回队尾元素
    int back()
    {
        return l.back();
    }
};

// 实际刷题时更常见的写法，常数时间好
// 如果可以确定加入操作的总次数不超过 n，那么可以用
// 一般笔试、面试都会有一个明确数据量，所以这是最常用的方式
class Queue2
{
private:
    int* q; 
    int l, r;

public:
    // 加入操作的总次数上限是多少，一定要明确
    Queue2(int n)
    {
        q = new int[n];
        l = r = 0;
    }

    // 调用任何方法之前，先调用这个方法来判断队列内是否有东西
    bool empty()
    {
        return l == r;
    }

    void push(int x)
    {
        q[r++] = x;
    }

    int poll()
    {
        return q[l++];
    }

    int front()
    {
        return q[l];
    }

    int back()
    {
        return q[r - 1];
    }

    int size()
    {
        return r - l;
    }
};

// 直接用 C++ 内部的实现
// stack 的底层实现其实就是动态数组 vector，不过常数时间并不好
class Stack1
{
private:
    stack<int> st;

public:
    // 调用任何方法之前，先调用这个方法来判断栈内是否有东西
    bool empty()
    {
        return st.empty();
    }

    void push(int x)
    {
        st.push(x);
    }

    // C++ 中的 pop 没有返回值
    int pop()
    {
        int ans = st.top();
        st.pop();
        return ans;
    }

    // 对应 Java 中的 peek 方法
    int top()
    {
        return st.top();
    }

    int size()
    {
        return st.size();
    }
};

// 实际刷题时更常见的写法，常数时间好
// 如果可以保证同时在栈里的元素个数不会超过 n，那么可以用
// 也就是发生弹出操作之后，空间可以复用
// 一般笔试、面试都会有一个明确数据量，所以这是最常用的方式
class Stack2
{
private:
    int* st;
    int sz;

public:
    // 同时在栈里的元素个数不会超过 n
    Stack2(int n)
    {
        st = new int[n];
        sz = 0;
    }

    // 调用任何方法之前，先调用这个方法来判断栈内是否有东西
    bool empty()
    {
        return sz == 0;
    }

    void push(int x)
    {
        st[sz++] = x;
    }

    int pop()
    {
        return st[--sz];
    }

    int top()
    {
        return st[sz - 1];
    }

    int size()
    {
        return sz;
    }
};

// 设计循环队列
// 测试链接 : https://leetcode.cn/problems/design-circular-queue/
class MyCircularQueue 
{
private:
    int* q;
    int l, r, sz, limit;

public:
    MyCircularQueue(int k) 
    {
        q = new int[k];
        l = r = sz = 0;
        limit = k;
    }
    
    // 如果队列满了，什么也不做，返回 false
    // 如果队列没满，加入 value，返回 true
    bool enQueue(int value) 
    {
        if(isFull()) return false;
        else
        {
            q[r] = value;
            // r++, 结束了，跳回 0
            r = r == limit - 1 ? 0 : (r + 1);
            ++sz;
            return true;
        }
    }

    // 如果队列空了，什么也不做，返回 false
    // 如果队列没空，弹出头部的数字，返回 true
    bool deQueue() 
    {
        if(isEmpty()) return false;
        else
        {
            // l++, 结束了，跳回 0
            l = l == limit - 1 ? 0 : (l + 1);
            --sz;
            return true;
        }
    }
    
    // 返回队列头部的数字（不弹出），如果没有数返回 -1
    int Front() 
    {
        if(isEmpty()) return -1;
        else return q[l];
    }
    
    int Rear() 
    {
        if(isEmpty()) return -1;
        else
        {
            int last = r == 0 ? (limit - 1) : (r - 1);
            return q[last];
        }
    }
    
    bool isEmpty() 
    {
        return sz == 0;
    }
    
    bool isFull() 
    {
        return sz == limit;
    }
};
